package com.ls.eightSort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * 桶排序
 */
public class Radix {

    public static void main(String[] args) {
        int arr[] = new int[800000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*800000000);
        }
//        show(arr);
        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        // 测试运行时间
        System.out.println("开始时间："+dateFormat.format(new Date()));
        sort(arr);
        System.out.println("结束时间："+dateFormat.format(new Date()));
//        show(arr);
    }

    public static void sort(int[] arr){
        // 定义桶
        int[][] bucket = new int[10][arr.length];
        // 定义每个桶的数量
        int[] bucketCount = new int[10];
        int index = 0;
        
        // 找出最大位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                max = arr[i];
            }
        }

        for (int i = 1, n = 1; i <= (max+"").length() ; i++,n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                // 将个位放入桶中
                int i1 = arr[j] /n % 10;
                bucket[i1][bucketCount[i1]] = arr[j];
                bucketCount[i1]++;
            }
            // 再取回给arr
            index = 0;
            for (int j = 0; j < bucket.length; j++) {
                if (bucketCount[j]>0){
                    for (int z = 0; z < bucketCount[j] ; z++) {
                        arr[index] = bucket[j][z];
                        index++;
                    }
                }
                // 排完序置为0
                bucketCount[j] = 0;
            }
        }

//        // 第一轮
//        for (int i = 0; i < arr.length; i++) {
//            // 将个位放入桶中
//            int i1 = arr[i] % 10;
//            bucket[i1][bucketCount[i1]] = arr[i];
//            bucketCount[i1]++;
//        }
//        // 再取回给arr
//        index = 0;
//        for (int i = 0; i < bucket.length; i++) {
//            if (bucketCount[i]>0){
//                for (int j = 0; j < bucketCount[i] ; j++) {
//                    arr[index] = bucket[i][j];
//                    index++;
//                }
//            }
//            // 排完序置为0
//            bucketCount[i] = 0;
//        }
        
        
        
//        // 第二轮
//        for (int i = 0; i < arr.length; i++) {
//            // 将个位放入桶中
//            int i1 = arr[i] /10 % 10;
//            bucket[i1][bucketCount[i1]] = arr[i];
//            bucketCount[i1]++;
//        }
//        // 再取回给arr
//        index = 0;
//        for (int i = 0; i < bucket.length; i++) {
//            if (bucketCount[i]>0){
//                for (int j = 0; j < bucketCount[i] ; j++) {
//                    arr[index] = bucket[i][j];
//                    index++;
//                }
//            }
//            bucketCount[i] = 0;
//        }
//
//        // 第三论
//        for (int i = 0; i < arr.length; i++) {
//            // 将个位放入桶中
//            int i1 = arr[i] /100;
//            bucket[i1][bucketCount[i1]] = arr[i];
//            bucketCount[i1]++;
//        }
//        // 再取回给arr
//        index = 0;
//        for (int i = 0; i < bucket.length; i++) {
//            if (bucketCount[i]>0){
//                for (int j = 0; j < bucketCount[i] ; j++) {
//                    arr[index] = bucket[i][j];
//                    index++;
//                }
//            }
//            bucketCount[i] = 0;
//        }
    }

    public static void show(int[] arr){
        for (int i : arr) {
            System.out.print(i+",");
        }
        System.out.println();

    }
}
